package leetcode.shuangpoint;

import java.util.*;

/**
 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。
 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

 输入：s = "ADOBECODEBANC", t = "ABC"
 输出："BANC"
 */
public class MinWindow {


    public static void main(String[] args) {
        String s = "ADOBECODEBANC" ;
        String t = "ABC";
        String res = new MinWindow().minWindow(s, t);

        System.out.println(res);
    }

    int[] need = new int[128];
    int[] have = new int[128];
    //结果字符串的开始位置和结束位置
    int start = -1,end = -1,count = Integer.MAX_VALUE;

    public String minWindow(String s, String t) {

        int len = s.length();

        //将目标字符串指定字符的出现次数记录
        for (int i = 0; i < t.length(); i++) {
            need[t.charAt(i)]++;
        }

        int i=0,j=0; //s[i..j] 是否白喊 t
        have[s.charAt(i)]++;

        boolean flag = false;
        while (i<len && j<len){

            if(need[s.charAt(j)]==0){//目标字符串没有这个字符
                if(++j<len)
                    have[s.charAt(j)]++;
                continue;
            }

            if(check()){
               if(j+1-i<count){
                   start = i;
                   end = j;
                   count = j+1-i;
               }

                have[s.charAt(i++)]--;//前指针向后移动
                flag = true;
            }else {
                if(++j<len)
                    have[s.charAt(j)]++;//后指针向后移动
            }
        }
        if(!flag)
            return "";

        return   s.substring(start, end + 1);
    }


    private boolean check(){
        for (int i = 0; i < need.length; i++) {
            if(have[i]<need[i])
                return false;
        }
        return  true;
    }
}